package com.lql.linkedtable;

import java.util.Stack;

/**
 * 单向链表的增删改查
 */
public class SingleLinkedTableDemo {
    public static void main(String[] args) {
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "林冲", "豹子头");
        HeroNode hero3 = new HeroNode(3, "武松", "啊哈哈");
        HeroNode hero4 = new HeroNode(4, "鲁智深", "啊嘿嘿");
        SingleLinkedTable singleLinkedTable = new SingleLinkedTable();
        singleLinkedTable.addNodeByNo(hero2);
        singleLinkedTable.addNodeByNo(hero1);
        singleLinkedTable.addNodeByNo(hero3);
        singleLinkedTable.addNodeByNo(hero4);
        singleLinkedTable.showNode();
        System.out.println("________________________");
        HeroNode heroNew = new HeroNode(2, "冲冲", "豹子头");
        singleLinkedTable.updateNode(heroNew);
        singleLinkedTable.showNode();

        System.out.println("________________________");
        singleLinkedTable.deleteNode(2);
        singleLinkedTable.showNode();
        System.out.println(singleLinkedTable.countNode());
        System.out.println("________________________");
        System.out.println(singleLinkedTable.findLastIndexNode(1));
        singleLinkedTable.reversePrintSingleLinked();

        System.out.println("_________逆转链表后___________");
        singleLinkedTable.reverseSingleLinkedNode();
        singleLinkedTable.showNode();

    }
}

class SingleLinkedTable {
    private final HeroNode head = new HeroNode(0, "", "");

    /**
     * 按照插入顺序插入节点，无序
     *
     * @param heroNode 待插入的节点
     */
    public void addNode(HeroNode heroNode) {
        HeroNode temp = head;
        while (temp.getNext() != null) {
            temp = temp.getNext();
        }
        temp.setNext(heroNode);
    }

    /**
     * 按照顺序添加英雄
     *
     * @param heroNode 待插入的节点
     */
    public void addNodeByNo(HeroNode heroNode) {
        HeroNode temp = head;
        //标志节点是否已经存在
        boolean flag = false;
        while (true) {
            if (temp.getNext() == null) {
                // 已经遍历到尾节点，新插入节点应在在链表尾部
                break;
            }
            if (temp.getNext().getNo() > heroNode.getNo()) {
                //找出插入位置节点的前一个节点
                break;
            } else if (temp.getNext().getNo() == heroNode.getNo()) {
                //节点已经存在这个编号的节点，无法插入
                flag = true;
                break;
            }
            //继续向下遍历
            temp = temp.getNext();
        }
        if (flag) {
            throw new RuntimeException("节点已经存在，插入失败");
        }
        // hero.next = temp.next
        heroNode.setNext(temp.getNext());
        // temp.next = hero
        temp.setNext(heroNode);
    }

    /**
     * 根据节点编号no，修改节点信息
     *
     * @param heroNode 待修改的节点
     */
    public void updateNode(HeroNode heroNode) {
        HeroNode temp = head.getNext();
        //标志待修改节点是否找到
        boolean flag = false;
        //链表为空
        if (temp == null) {
            throw new RuntimeException("链表为空，修改失败");
        }
        while (true) {
            if (temp == null) {
                //链表遍历到表尾未找到
                break;
            }
            if (temp.getNo() == heroNode.getNo()) {
                //插入位置已经找到
                flag = true;
                break;
            }
            temp = temp.getNext();
        }
        if (!flag) {
            //不存在该节点
            throw new RuntimeException("不存在该节点，修改失败");
        }
        temp.setName(heroNode.getName());
        temp.setNickName(heroNode.getNickName());
    }

    /**
     * 根据编号删除节点
     *
     * @param no 待删除节点的编号
     */
    public void deleteNode(int no) {
        if (head.getNext() == null) {
            //链表为空
            throw new RuntimeException("链表为空，删除失败");
        }
        HeroNode temp = head;
        //标志待删除节点是否找到
        boolean flag = false;
        while (true) {
            if (temp.getNext() == null) {
                // 链表遍历到结尾，未找到待删除结点
                break;
            }
            if (temp.getNext().getNo() == no) {
                //找到待删除结点
                flag = true;
                break;
            }
            temp = temp.getNext();
        }
        if (!flag) {
            throw new RuntimeException("不存在该节点，删除失败");
        }
        // temp.next = temp.next.next
        temp.setNext(temp.getNext().getNext());
    }

    /**
     * 获取链表节点中元素个数
     *
     * @return
     */
    public int countNode() {
        HeroNode temp = head.getNext();
        int count = 0;
        while (temp != null) {
            count++;
            temp = temp.getNext();
        }
        return count;
    }

    /**
     * 获取倒数第index数的节点
     *
     * @param index 倒数第几个节点
     * @return
     */
    public HeroNode findLastIndexNode(int index) {
        if (head.getNext() == null) {
            throw new RuntimeException("链表为空，出现异常");
        }
        // 链表中有效节点数
        int count = countNode();
        // index的数据校验
        if (index > count || index <= 0) {
            throw new RuntimeException("index数目有问题");
        }
        HeroNode temp = head.getNext();
        int i = count - index;
        while (i > 0) {
            temp = temp.getNext();
            i--;
        }
        return temp;
    }


    /**
     * 逆转单链表
     */
    public void reverseSingleLinkedNode() {
        //链表为空或只有单个元素，无需逆转，直接返回
        if (head.getNext() == null || head.getNext().getNext() == null) {
            return;
        }
        // 定义一个逆转链表的头节点
        HeroNode reverseHead = new HeroNode(0, "", "");
        //当前节点
        HeroNode currentNode = head.getNext();
        //用来记录当前节点的下一个节点
        HeroNode next = null;
        while (currentNode != null) {
            next = currentNode.getNext();
            // currentNode.next = reverseHead.next
            currentNode.setNext(reverseHead.getNext());
            // reverseHead.next = currentNode
            reverseHead.setNext(currentNode);
            currentNode = next;
        }
        // 将逆转链表的头节点改变为原来的头节点
        // head.next = reverseHead.Next
        head.setNext(reverseHead.getNext());
    }

    /**
     * 逆序打印单链表
     */
    public void reversePrintSingleLinked() {
        //链表为空
        if (head.getNext() == null) {
            return;
        }
        // 定义一个栈，使用栈进行逆序
        Stack<HeroNode> heroNodes = new Stack<>();
        HeroNode temp = head.getNext();
        while (temp!=null){
            heroNodes.push(temp);
            temp = temp.getNext();
        }
        while (heroNodes.size()>0){
            System.out.println(heroNodes.pop());
        }
    }

    /**
     * 展示链表
     */
    public void showNode() {
        HeroNode next = head.getNext();
        while (next != null) {
            System.out.println(next);
            next = next.getNext();
        }
    }
}

class HeroNode {
    private int no;
    private String name;
    private String nickName;
    private HeroNode next;

    public HeroNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getNickName() {
        return nickName;
    }

    public void setNickName(String nickName) {
        this.nickName = nickName;
    }

    public HeroNode getNext() {
        return next;
    }

    public void setNext(HeroNode next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}